package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/minimum-score-of-a-path-between-two-cities/description/
 * @create 2025/9/18 21:42
 * @since JDK17
 */

public class Solution06 {
    int ans = Integer.MAX_VALUE, n;
    List<List<int[]>> g = new ArrayList<>();
    boolean[] vis;

    void dfs(int cur) {
        vis[cur] = true;
        var list = g.get(cur);
        for (int[] next : list) {
            ans = Math.min(ans, next[1]);
            if (!vis[next[0]]) {
                dfs(next[0]);
            }
        }
    }
    public int minScore(int n, int[][] roads) {
        int m = roads.length;
        this.n = n;
        vis = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            g.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int from = roads[i][0], to = roads[i][1], val = roads[i][2];
            g.get(from).add(new int[]{to, val});
            g.get(to).add(new int[]{from, val});
        }
        dfs(1);
        return ans;
    }
}
